package com.hqq.exercise.array;

/**
 * RotateArray 旋转数组的最小数字
 * 题目描述:把一个数组最开始的若干个元素搬到数组的末尾 我们称之为数组的旋转
 * 输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素
 * 思路:使用二分查找
 * 样例输入:
 * {3,4,5,1,2}
 * 样例输出:
 * 1
 * Created by heqianqian on 2017/8/10.
 */
public class RotateArray {

    public static int minElementInRotateArray(int[] array) {
        int leftIndex = 0, rightIndex = array.length - 1, midIndex = (rightIndex + leftIndex) / 2;
        while (leftIndex < rightIndex - 1) {
            if (array[leftIndex] == array[midIndex] && array[rightIndex] == array[midIndex]) {
                //三者相同 无法判断 因此进行顺序查找
                return minElementBySort(array);
            } else {
                if (array[midIndex] >= array[leftIndex]) {
                    leftIndex = midIndex;
                } else {
                    rightIndex = midIndex;
                }
                midIndex = (rightIndex + leftIndex) / 2;
            }
        }
        return array[rightIndex];
    }

    private static int minElementBySort(int[] ints) {
        int minElement = ints[0];
        for (int i = 1; i < ints.length; i++) {
            if (ints[i] < minElement) {
                minElement = ints[i];
            }
        }
        return minElement;
    }

}
